#include <iostream>
#include <vector>

using namespace std;
// 997. 找到小镇的法官
// 小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
// 给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
//如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。
class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> indegree(n+1,0);    // 顶点的入度
        vector<int> outdegree(n+1,0);   // 顶点的出度

        for(int i = 0; i < trust.size(); i++) {
            outdegree[trust[i][0]]++;
            indegree[trust[i][1]]++;
        }
        // 找到入度为n-1，出度为0的顶点
        for(int i = 1; i <= n; i++) {
            if(outdegree[i] == 0 && indegree[i] == n-1)
                return i;
        }
        return -1;
    }
};

int main() {
    vector<vector<int>> trust1({{1,2}});
    cout << Solution().findJudge(2,trust1) << endl; // 2

    vector<vector<int>> trust2({{1,3},{2,3}});
    cout << Solution().findJudge(3,trust2) << endl; // 3

    vector<vector<int>> trust3({{1,3},{2,3},{3,1}});
    cout << Solution().findJudge(3,trust3) << endl; // -1
    return 0;
}
